AUTHORS: Abdelkader Lamamri, Imene Mehamdia

Download as PDF

ABSTRACT: The airline crew pairing problem with time windows is solved using a mixed linear programming method. The problem is to cover cost of all flights of the company. Given the large size of the problems encountered in industry, these models are solved by an approach based on column generation that can handle implicitly all feasible solutions and a master problem determining the best solution. We present a new approach to improve the acceleration of the method of column generation problem for the construction crew pairing, it is projected in each arc, the resources on a vector of dimension less using a Lagrangean relaxation algorithm to determine the coefficients of the projection arc combined with an algorithm for re-optimization, well generates a subset of complementary solutions to the master problem. The computational experiments were conducted on a broad range of instances, many of them published in the literature. They show a significant reduction of the number of column generation iterations and computing time.

KEYWORDS: Column generation, Crew pairing problem, Mathematical programming, Lagrangean relaxation

REFERENCES:

[1] DESAULNIERS G., DESROSIERS J., DUMAS Y., MARC S., RIOUX B., SOLOMON M., SOUMIS F., «Crew Pairing at Air France », European Journal of Operational Research, vol. 97, p. 245–259, 1997.

[2] LAVOIE S., MINOUX M., ODIER E., « A new approach for crew pairing problems by column generation with an application to air transportation », European Journal of Operational Research, vol. 35, p. 45–58, 1988.

[3] LOISEAU I., CESELLI A., N.MACULAN, SALANI M., « Génération de colonnes en programmation linéaire en nombres entiers », PASCHOS V. T., Ed., Optimisation combinatoire : Concepts fondamentaux, Hermès, Paris, 2005.